Search Results

Documents authored by Gregor, Petr

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.33
Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections

Authors: Petr Gregor, Torsten Mütze, and Namrata

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
In this paper we propose a notion of pattern avoidance in binary trees that generalizes the avoidance of contiguous tree patterns studied by Rowland and non-contiguous tree patterns studied by Dairyko, Pudwell, Tyner, and Wynn. Specifically, we propose algorithms for generating different classes of binary trees that are characterized by avoiding one or more of these generalized patterns. This is achieved by applying the recent Hartung-Hoang-Mütze-Williams generation framework, by encoding binary trees via permutations. In particular, we establish a one-to-one correspondence between tree patterns and certain mesh permutation patterns. We also conduct a systematic investigation of all tree patterns on at most 5 vertices, and we establish bijections between pattern-avoiding binary trees and other combinatorial objects, in particular pattern-avoiding lattice paths and set partitions.
Cite as

Petr Gregor, Torsten Mütze, and Namrata. Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ISAAC.2023.33,
  author =	{Gregor, Petr and M\"{u}tze, Torsten and Namrata},
  title =	{{Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.33},
  URN =		{urn:nbn:de:0030-drops-193350},
  doi =		{10.4230/LIPIcs.ISAAC.2023.33},
  annote =	{Keywords: Generation, binary tree, pattern avoidance, permutation, bijection}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.54
The Hamilton Compression of Highly Symmetric Graphs

Authors: Petr Gregor, Arturo Merino, and Torsten Mütze

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We say that a Hamilton cycle C = (x₁,…,x_n) in a graph G is k-symmetric, if the mapping x_i ↦ x_{i+n/k} for all i = 1,…,n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x₁,…,x_n equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k-fold rotational symmetry, i.e., all information about the graph is compressed into a 360^∘/k wedge of the drawing. We refer to the maximum k for which there exists a k-symmetric Hamilton cycle in G as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases we determine their Hamilton compression exactly, and in other cases we provide close lower and upper bounds. The cycles we construct have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced.
Cite as

Petr Gregor, Arturo Merino, and Torsten Mütze. The Hamilton Compression of Highly Symmetric Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.MFCS.2022.54,
  author =	{Gregor, Petr and Merino, Arturo and M\"{u}tze, Torsten},
  title =	{{The Hamilton Compression of Highly Symmetric Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.54},
  URN =		{urn:nbn:de:0030-drops-168529},
  doi =		{10.4230/LIPIcs.MFCS.2022.54},
  annote =	{Keywords: Hamilton cycle, Gray code, hypercube, permutahedron, Johnson graph, Cayley graph, abelian group, vertex-transitive}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.34
Star Transposition Gray Codes for Multiset Permutations

Authors: Petr Gregor, Torsten Mütze, and Arturo Merino

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Given integers k ≥ 2 and a_1,…,a_k ≥ 1, let a: = (a_1,…,a_k) and n: = a_1+⋯+a_k. An a-multiset permutation is a string of length n that contains exactly a_i symbols i for each i = 1,…,k. In this work we consider the problem of exhaustively generating all a-multiset permutations by star transpositions, i.e., in each step, the first entry of the string is transposed with any other entry distinct from the first one. This is a far-ranging generalization of several known results. For example, it is known that permutations (a_1 = ⋯ = a_k = 1) can be generated by star transpositions, while combinations (k = 2) can be generated by these operations if and only if they are balanced (a_1 = a_2), with the positive case following from the middle levels theorem. To understand the problem in general, we introduce a parameter Δ(a): = n-2max{a_1,…,a_k} that allows us to distinguish three different regimes for this problem. We show that if Δ(a) < 0, then a star transposition Gray code for a-multiset permutations does not exist. We also construct such Gray codes for the case Δ(a) > 0, assuming that they exist for the case Δ(a) = 0. For the case Δ(a) = 0 we present some partial positive results. Our proofs establish Hamilton-connectedness or Hamilton-laceability of the underlying flip graphs, and they answer several cases of a recent conjecture of Shen and Williams. In particular, we prove that the middle levels graph is Hamilton-laceable.
Cite as

Petr Gregor, Torsten Mütze, and Arturo Merino. Star Transposition Gray Codes for Multiset Permutations. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.STACS.2022.34,
  author =	{Gregor, Petr and M\"{u}tze, Torsten and Merino, Arturo},
  title =	{{Star Transposition Gray Codes for Multiset Permutations}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.34},
  URN =		{urn:nbn:de:0030-drops-158448},
  doi =		{10.4230/LIPIcs.STACS.2022.34},
  annote =	{Keywords: Gray code, permutation, combination, transposition, Hamilton cycle}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.60
On the Central Levels Problem

Authors: Petr Gregor, Ondřej Mička, and Torsten Mütze

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
The central levels problem asserts that the subgraph of the (2m+1)-dimensional hypercube induced by all bitstrings with at least m+1-𝓁 many 1s and at most m+𝓁 many 1s, i.e., the vertices in the middle 2𝓁 levels, has a Hamilton cycle for any m ≥ 1 and 1 ≤ 𝓁 ≤ m+1. This problem was raised independently by Savage, by Gregor and Škrekovski, and by Shen and Williams, and it is a common generalization of the well-known middle levels problem, namely the case 𝓁 = 1, and classical binary Gray codes, namely the case 𝓁 = m+1. In this paper we present a general constructive solution of the central levels problem. Our results also imply the existence of optimal cycles through any sequence of 𝓁 consecutive levels in the n-dimensional hypercube for any n ≥ 1 and 1 ≤ 𝓁 ≤ n+1. Moreover, extending an earlier construction by Streib and Trotter, we construct a Hamilton cycle through the n-dimensional hypercube, n≥ 2, that contains the symmetric chain decomposition constructed by Greene and Kleitman in the 1970s, and we provide a loopless algorithm for computing the corresponding Gray code.
Cite as

Petr Gregor, Ondřej Mička, and Torsten Mütze. On the Central Levels Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ICALP.2020.60,
  author =	{Gregor, Petr and Mi\v{c}ka, Ond\v{r}ej and M\"{u}tze, Torsten},
  title =	{{On the Central Levels Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.60},
  URN =		{urn:nbn:de:0030-drops-124678},
  doi =		{10.4230/LIPIcs.ICALP.2020.60},
  annote =	{Keywords: Gray code, Hamilton cycle, hypercube, middle levels, symmetric chain decomposition}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.66
Gray Codes and Symmetric Chains

Authors: Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, and Kaja Wille

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider the problem of constructing a cyclic listing of all bitstrings of length 2n+1 with Hamming weights in the interval [n+1-l,n+l], where 1 <= l <= n+1, by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (l=1). We provide a solution for the case l=2 and solve a relaxed version of the problem for general values of l, by constructing cycle factors for those instances. Our proof uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets, and we present several new constructions of such decompositions. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the n-dimensional hypercube for any n >= 12.
Cite as

Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, and Kaja Wille. Gray Codes and Symmetric Chains. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ICALP.2018.66,
  author =	{Gregor, Petr and J\"{a}ger, Sven and M\"{u}tze, Torsten and Sawada, Joe and Wille, Kaja},
  title =	{{Gray Codes and Symmetric Chains}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.66},
  URN =		{urn:nbn:de:0030-drops-90703},
  doi =		{10.4230/LIPIcs.ICALP.2018.66},
  annote =	{Keywords: Gray code, Hamilton cycle, hypercube, poset, symmetric chain}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.40
Trimming and Gluing Gray Codes

Authors: Petr Gregor and Torsten Mütze

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We consider the algorithmic problem of generating each subset of [n]:={1,2,...,n} whose size is in some interval [k,l], 0 <= k <= l <= n, exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For k=0 and l=n this is the classical problem of generating all 2^n subsets of [n] by element additions/removals, and for k=l this is the classical problem of generating all n over k subsets of [n] by element exchanges. We prove the existence of such cyclic minimum-change enumerations for a large range of values n, k, and l, improving upon and generalizing several previous results. For all these existential results we provide optimal algorithms to compute the corresponding Gray codes in constant time O(1) per generated set and space O(n). Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Q_n induced by all levels [k,l]. We reduce all remaining open cases to a generalized version of the middle levels conjecture, which asserts that the subgraph of Q_(2k+1) induced by all levels [k-c,k+1+c], c in {0, 1, ... , k}, has a Hamilton cycle. We also prove an approximate version of this conjecture, showing that this graph has a cycle that visits a (1-o(1))-fraction of all vertices.
Cite as

Petr Gregor and Torsten Mütze. Trimming and Gluing Gray Codes. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.STACS.2017.40,
  author =	{Gregor, Petr and M\"{u}tze, Torsten},
  title =	{{Trimming and Gluing Gray Codes}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.40},
  URN =		{urn:nbn:de:0030-drops-69930},
  doi =		{10.4230/LIPIcs.STACS.2017.40},
  annote =	{Keywords: Gray code, subset, combination, loopless algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact